﻿#include"C++.h"


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//string 模拟实现
//#include"string.h"
//
//namespace wzz_s
//{
//	void test_string1()
//	{
//		string s1;
//		string s2("hello world");
//		cout << s1.c_str() << endl;
//		cout << s2.c_str() << endl;
//
//		for (size_t i = 0; i < s2.size(); ++i)
//		{
//			s2[i] += 2;
//			cout << s2.c_str() << endl;
//		}
//
//		for (auto e : s2)
//		{
//			cout << e << " ";
//		}
//		cout << endl;
//
//		string::iterator it = s2.begin();
//		while (it != s2.end())
//		{
//			//*it+=2;
//			cout << *it << " ";
//			++it;
//		}
//		cout << endl;
//	}
//
//	void test_string2()
//	{
//		string s1("hello world");
//		s1 += 'x';
//		s1 += '#';
//		cout << s1.c_str() << endl;
//
//		s1 += " hello	";
//		cout << s1.c_str() << endl;
//
//		s1.insert(5, '&');
//		cout << s1.c_str() << endl;
//
//		s1.erase(5, 4);
//		cout << s1.c_str() << endl;
//
//		/*s1.erase(5, 100);
//		cout << s1.c_str() << endl;*/
//
//		s1.erase(5);
//		cout << s1.c_str() << endl;
//	}
//
//	void test_string3()
//	{
//		string s("test.cpp.zip");
//		size_t pos = s.find('.');
//		string suffix = s.substr(pos);
//		cout << suffix.c_str()<< endl;
//		string copy(s);
//		cout << copy.c_str() << endl;
//	}
//
//	void test_string4()
//	{
//		string s1("hello world");
//		string s2("hello world");
//
//		cout << (s1 < s2) << endl;
//		cout << (s1 == s2) << endl;
//		cout << (s1 == "hello world") << endl;
//		cout << ("hello world"< s2) << endl;
//
//		cout << s1 << s2 << endl;
//		cin >> s1;
//		cout << s1 << endl;
//	}
//
//	void test_string5()
//	{
//		string s1("hello world");
//		string s2 = s1;
//
//		cout << s1 << endl;
//		cout << s2 << endl;
//	}
//}

//int main()
//{
//	//wzz_s::test_string1();
//	//wzz_s::test_string2();
//	//wzz_s::test_string3();
//	//wzz_s::test_string4();
//	//wzz_s::test_string5();
//
//	return 0;
//}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//vector

//void test_vector1()
//{
//	vector<int> v1;
//	vector<int> v2(10, 1);
//
//	vector<int> v3(++v2.begin(), --v2.end());
//
//	for (size_t i = 0; i < v3.size(); i++)
//	{
//		cout << v3[i] << ' ';
//	}
//	cout << endl;
//
//	vector<int>::iterator it = v3.begin();
//	while (it != v3.end())
//	{
//		cout << *it << ' ';
//		++it;
//	}
//	cout << endl;
//
//	for (auto e : v3)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//
//
//}
//
//// 测试vector的默认扩容机制
//void TestVectorExpand()
//{
//	size_t sz;
//	vector<int> v;
//	v.reserve(100);
//	sz = v.capacity();
//	cout << "making v grow:\n";
//	for (int i = 0; i < 100; ++i)
//	{
//		v.push_back(i);
//		if (sz != v.capacity())
//		{
//			sz = v.capacity();
//			cout << "capacity changed: " << sz << '\n';
//		}
//	}
//}
//void test_vector2()
//{
//	//TestVectorExpand();
//	vector<int> v(10, 1);
//	v.reserve(20);
//	cout << v.size() << endl;
//	cout << v.capacity() << endl;
//
//	v.resize(15,2);
//	cout << v.size() << endl;
//	cout << v.capacity() << endl;
//
//	v.resize(25,3);
//	cout << v.size() << endl;
//	cout << v.capacity() << endl;
//
//	v.resize(5, 4);
//	cout << v.size() << endl;
//	cout << v.capacity() << endl;
//}
//
//void test_vector3()
//{
//	vector<int>v(10, 1);
//	v.push_back(2);
//	v.insert(v.begin(), 0);
//
//	for (auto e : v)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//
//	v.insert(v.begin()+3, 10);
//
//	for (auto e : v)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//
//	vector<int>v1(5, 0);
//	for (size_t i = 0; i < 5; i++)
//	{
//		cin >> v1[i];
//	}
//
//	for (auto e : v1)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//}
//
//void test_vector4()
//{
//	vector<string>v1;
//	string s1("xxxx");
//	v1.push_back(s1);
//
//	v1.push_back("yyyyy");
//
//	for (auto e : v1)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//
//	//二维数组
//	vector<int> v(5, 1);
//	vector<vector<int>> vv(10,v);
//	vv[2][1] = 2;
//	//vv.operator[](2).operator[](1) = 2;
//	for (size_t i = 0; i < vv.size(); ++i)
//	{
//		for (size_t j = 0; j < vv[i].size(); j++)
//		{
//			cout << vv[i][j] << ' ';
//		}
//		cout << endl;
//	}
//	cout << endl;
//}

//vector的模拟实现
//#include"vector.h"
//
//int main()
//{
//	//test_vector1();
//	//test_vector2();
//	//test_vector3();
//	//test_vector4();
//	//wzz_v::test_vector5();
//	//wzz_v::test_vector6();
//	//wzz_v::test_vector7();
//	//wzz_v::test_vector8();
//	//wzz_v::test_vector9();
//	//wzz_v::test_vector10();
//	//wzz_v::test_vector11();
//	return 0;
//}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// list

//void test_list1()
//{
//	list<int> lt;
//	lt.push_back(1);
//	lt.push_back(2);
//	lt.push_back(3);
//	lt.push_back(4);
//
//	list<int>::iterator it = lt.begin();
//	while (it != lt.end())
//	{
//		cout << *it << " ";
//		++it;
//	}
//	cout << endl;
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	//不支持，要求随机迭代器
//	//sort(lt.begin(), lt.end());
//	string s("dadawdf");
//	cout << s << endl;
//	sort(s.begin(), s.end());
//	cout << s << endl;
//}
//
//struct A
//{
//public:
//	A(int a1 = 1, int a2 = 1)
//		:_a1(a1)
//		, _a2(a2)
//	{
//		cout << "A(int a1 = 1, int a2 = 1)" << endl;
//	}
//
//	A(const A& aa)
//		:_a1(aa._a1)
//		, _a2(aa._a2)
//	{
//		cout << "A(const A& aa)" << endl;
//	}
//
//	int _a1;
//	int _a2;
//};
//
//void test_list2()
//{
//	/*list<int> lt;
//	lt.push_back(1);
//	lt.emplace_back(2);
//	lt.emplace_back(3);
//	lt.emplace_back(4);
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;*/
//
//	list<A> lt;
//	A aa1(1, 1);
//	lt.push_back(aa1);
//	lt.push_back(A(2, 2));
//	//lt.push_back(3, 3);
//
//	lt.emplace_back(aa1);
//	lt.emplace_back(A(2, 2));
//	cout << endl;
//	// 支持直接传构造A对象的参数emplace_back
//	lt.emplace_back(3, 3);
//}
//
//void test_list3()
//{
//	list<int> lt;
//	lt.push_back(1);
//	lt.push_back(2);
//	lt.push_back(3);
//	lt.push_back(4);
//	lt.push_back(5);
//	lt.push_back(6);
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	auto it = lt.begin();
//	int k = 3;
//	while (k--)
//	{
//		++it;
//	}
//
//	lt.insert(it, 30);
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	int x = 0;
//	cin >> x;
//	it = find(lt.begin(), lt.end(), x);
//	if (it != lt.end())
//	{
//		lt.erase(it);
//	}
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
//
//void test_list4()
//{
//	list<int> lt;
//	lt.push_back(1);
//	lt.push_back(20);
//	lt.push_back(3);
//	lt.push_back(5);
//	lt.push_back(4);
//	lt.push_back(5);
//	lt.push_back(6);
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	// 默认升序
//	// lt.sort();
//	// 降序 - 仿函数
//	// less<int> ls;
//	// greater<int> gt;
//	// lt.sort(gt);
//	lt.sort(greater<int>());
//
//	// lt.reverse();
//	//reverse(lt.begin(), lt.end());
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	std::list<double> first, second;
//
//	first.push_back(3.1);
//	first.push_back(2.2);
//	first.push_back(2.9);
//
//	second.push_back(3.7);
//	second.push_back(7.1);
//	second.push_back(1.4);
//
//	first.sort();
//	second.sort();
//
//	first.merge(second);
//}
//
//void test_list5()
//{
//	list<int> lt;
//	lt.push_back(1);
//	lt.push_back(20);
//	lt.push_back(3);
//	lt.push_back(5);
//	lt.push_back(5);
//	lt.push_back(5);
//	lt.push_back(4);
//	lt.push_back(4);
//	lt.push_back(5);
//	lt.push_back(6);
//	lt.push_back(6);
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	lt.sort();
//	
//	lt.unique();
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;	
//}
//
//void test_list6()
//{
//	// 一个链表节点转移给另一个链表
//	std::list<int> mylist1, mylist2;
//	std::list<int>::iterator it;
//
//	// set some initial values:
//	for (int i = 1; i <= 4; ++i)
//		mylist1.push_back(i);      // mylist1: 1 2 3 4
//
//	for (int i = 1; i <= 3; ++i)
//		mylist2.push_back(i * 10);   // mylist2: 10 20 30
//
//	it = mylist1.begin();
//	++it;                         // points to 2
//
//	mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
//	// mylist2 (empty)
//	// "it" still points to 2 (the 5th element
//
//
//// 调整当前链表节点的顺序
//	list<int> lt;
//	lt.push_back(1);
//	lt.push_back(2);
//	lt.push_back(3);
//	lt.push_back(4);
//	lt.push_back(5);
//	lt.push_back(6);
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	int x = 0;
//	cin >> x;
//	it = find(lt.begin(), lt.end(), x);
//	if (it != lt.end())
//	{
//		//lt.splice(lt.begin(), lt, it);
//		lt.splice(lt.begin(), lt, it, lt.end());
//	}
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//}
//
//void test_op1()
//{
//	srand(time(0));
//	const int N = 1000000;
//
//	list<int> lt1;
//	vector<int> v;
//
//	for (int i = 0; i < N; ++i)
//	{
//		auto e = rand() + i;
//		lt1.push_back(e);
//		v.push_back(e);
//	}
//
//	int begin1 = clock();
//	// 排序
//	sort(v.begin(), v.end());
//	int end1 = clock();
//
//	int begin2 = clock();
//	lt1.sort();
//	int end2 = clock();
//
//	printf("vector sort:%d\n", end1 - begin1);
//	printf("list sort:%d\n", end2 - begin2);
//}
//
//void test_op2()
//{
//	srand(time(0));
//	const int N = 1000000;
//
//	list<int> lt1;
//	list<int> lt2;
//
//	for (int i = 0; i < N; ++i)
//	{
//		auto e = rand() + i;
//		lt1.push_back(e);
//		lt2.push_back(e);
//	}
//
//	int begin1 = clock();
//	// 拷贝vector
//	vector<int> v(lt2.begin(), lt2.end());
//
//	// 排序
//	sort(v.begin(), v.end());
//
//	// 拷贝回lt2
//	lt2.assign(v.begin(), v.end());
//
//	int end1 = clock();
//
//	int begin2 = clock();
//	lt1.sort();
//	int end2 = clock();
//
//	printf("list copy vector sort copy list sort:%d\n", end1 - begin1);
//	printf("list sort:%d\n", end2 - begin2);
//}
//
//#include"list.h"
//
//int main()
//{
//	//test_list1();
//	//test_list2();
//	//test_list3();
//	//test_list4();
//	//test_list5();
//	//test_list6();
//
//	//test_op1();
//	//test_op2();
//
//	//wzz_lt::test_list1();
//	//wzz_lt::test_list2();
//	//wzz_lt::test_list3();
//
//	return 0;
//}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//stack_queue

//#include"stack.h"
//#include"queue.h"


//int main()
//{
//	wzz_st::stack<int, vector<int>> st;
//
//	// 类模板实例化时，按需实例化，使用哪些成员函数就实例化哪些，不会全部实例化
//	st.push(1);
//	st.push(2);
//	st.push(3);
//	st.push(4);
//
//	
//	wzz_q::queue<int, list<int>> q;
//
//	q.push(1);
//	q.push(2);
//	q.push(3);
//	q.push(4);
//
//
//	return 0;
//}


//void test_op1()
//{
//	srand(time(0));
//	const int N = 1000000;
//
//	deque<int> dq;
//	vector<int> v;
//
//	for (int i = 0; i < N; ++i)
//	{
//		auto e = rand() + i;
//		v.push_back(e);
//		dq.push_back(e);
//	}
//
//	int begin1 = clock();
//	sort(v.begin(), v.end());
//	int end1 = clock();
//
//	int begin2 = clock();
//	sort(dq.begin(), dq.end());
//	int end2 = clock();
//
//	printf("vector:%d\n", end1 - begin1);
//	printf("deque:%d\n", end2 - begin2);
//}
//
//void test_op2()
//{
//	srand(time(0));
//	const int N = 1000000;
//
//	deque<int> dq1;
//	deque<int> dq2;
//
//	for (int i = 0; i < N; ++i)
//	{
//		auto e = rand() + i;
//		dq1.push_back(e);
//		dq2.push_back(e);
//	}
//
//	int begin1 = clock();
//	sort(dq1.begin(), dq1.end());
//	int end1 = clock();
//
//	int begin2 = clock();
//	// 拷贝到vector
//	vector<int> v(dq2.begin(), dq2.end());
//	sort(v.begin(), v.end());
//	dq2.assign(v.begin(), v.end());
//	int end2 = clock();
//
//	printf("deque sort:%d\n", end1 - begin1);
//	printf("deque copy vector sort, copy back deque:%d\n", end2 - begin2);
//}

//int main()
//{
//	//test_op1();
//	test_op2();
//	return 0;
//}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//priority_queue
//#include"priority_queue.h"


//int main()
//{
//	//priority_queue<int> pq;
//	wzz_pq::priority_queue<int, vector<int>, greater<int>> pq;	
//	//wzz_pq::priority_queue<int> pq;
//	pq.push(4);
//	pq.push(1);
//	pq.push(5);
//	pq.push(7);
//	pq.push(9);
//	while (!pq.empty())	
//	{
//		cout << pq.top() << " ";
//		pq.pop();
//	}
//	cout << endl;
//
//	return 0;
//}

//int main()
//{
//	int myints[] = { 10,20,30,5,15 };
//	sort(myints, myints + 5);
//
//	std::vector<int> v(myints, myints + 5);
//	cout << is_heap(v.begin(), v.end()) << endl;
//
//	cout << is_heap(myints, myints + 5) << endl;
//
//	make_heap(v.begin(), v.end());
//	cout << is_heap(v.begin(), v.end()) << endl;
//	std::sort_heap(v.begin(), v.end());
//	for (auto e : v)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//
//	return 0;
//}

// 仿函数：本质是一个类，这个类重载operator(),他的对象可以像函数一样使用
//template<class T>
//class Less
//{
//public:
//	bool operator()(const T& x, const T& y)
//	{
//		return x < y;
//	}
//};
//
//template<class T>
//class Greater
//{
//public:
//	bool operator()(const T& x, const T& y)
//	{
//		return x > y;
//	}
//};

 //< 升序
 //> 降序
//template<class Compare>
//void BubbleSort(int* a, int n, Compare com)
//{
//	for (int j = 0; j < n; j++)
//	{
//		// 单趟
//		int flag = 0;
//		for (int i = 1; i < n - j; i++)
//		{
//			//if (a[i] < a[i - 1])
//			if (com(a[i], a[i - 1]))
//			{
//				swap(a[i - 1], a[i]);
//				flag = 1;
//			}
//		}
//
//		if (flag == 0)
//		{
//			break;
//		}
//	}
//}

//int main()
//{
//	Less<int> LessFunc;
//	Greater<int> GreaterFunc;
//	// 函数对象
//	cout << LessFunc(1, 2) << endl;
//	cout << LessFunc.operator()(1, 2) << endl;
//
//	int a[] = { 9,1,2,5,7,4,6,3 };
//	BubbleSort(a, 8, LessFunc);
//	BubbleSort(a, 8, GreaterFunc);
//
//	BubbleSort(a, 8, Less<int>());
//	BubbleSort(a, 8, Greater<int>());
//
//	return 0;
//}


//int main()
//{
//	int myints[] = { 10,20,30,5,15 };
//	std::vector<int> v(myints, myints + 5);
//
//	std::make_heap(v.begin(), v.end());
//	std::cout << "initial max heap   : " << v.front() << '\n';
//
//	std::pop_heap(v.begin(), v.end()); v.pop_back();
//	std::cout << "max heap after pop : " << v.front() << '\n';
//
//	v.push_back(99); std::push_heap(v.begin(), v.end());
//	std::cout << "max heap after push: " << v.front() << '\n';
//
//	std::sort_heap(v.begin(), v.end());
//
//	std::cout << "final sorted range :";
//	for (unsigned i = 0; i < v.size(); i++)
//		std::cout << ' ' << v[i];
//
//	std::cout << '\n';
//	return 0;
//}


//class Date
//{
//	friend ostream& operator<<(ostream& _cout, const Date& d);
//public:
//	Date(int year = 1900, int month = 1, int day = 1)
//		: _year(year)
//		, _month(month)
//		, _day(day)
//	{}
//
//	bool operator<(const Date& d)const
//	{
//		return (_year < d._year) ||
//			(_year == d._year && _month < d._month) ||
//			(_year == d._year && _month == d._month && _day < d._day);
//	}
//
//	bool operator>(const Date& d)const
//	{
//		return (_year > d._year) ||
//			(_year == d._year && _month > d._month) ||
//			(_year == d._year && _month == d._month && _day > d._day);
//	}
//private:
//	int _year;
//	int _month;
//	int _day;
//};
//
//ostream& operator<<(ostream& _cout, const Date& d)
//{
//	_cout << d._year << "-" << d._month << "-" << d._day;
//	return _cout;
//}
//
//class DateLess
//{
//public:
//	bool operator()(Date* p1, Date* p2)
//	{
//		return *p1 < *p2;
//	}
//};
//
//
//int main()
//{
//	wzz_pq::priority_queue<Date> q1;
//	q1.push(Date(2018, 10, 29));
//	q1.push(Date(2018, 10, 28));
//	q1.push(Date(2018, 10, 30));
//	cout << q1.top() << endl;
//	q1.pop();
//
//	cout << q1.top() << endl;
//	q1.pop();
//
//	cout << q1.top() << endl;
//	q1.pop();
//
//	cout << endl;
//
//	// 1、类类型不支持比较大小
//	// 2、支持比较大小，但是比较的逻辑不是你想要的需要自己实现仿函数
//
//	//bit::priority_queue<Date*, vector<Date*>, DateLess> q2;
//	wzz_pq::priority_queue<Date*> q2;
//	q2.push(new Date(2018, 10, 29));
//	q2.push(new Date(2018, 10, 28));
//	q2.push(new Date(2018, 10, 30));
//	cout << *q2.top() << endl;
//	q2.pop();
//
//	cout << *q2.top() << endl;
//	q2.pop();
//
//	cout << *q2.top() << endl;
//	q2.pop();
//
//	wzz_pq::priority_queue<int*> q3;
//	q3.push(new int(2));
//	q3.push(new int(1));
//	q3.push(new int(3));
//
//	cout << *q3.top() << endl;
//	q3.pop();
//
//	cout << *q3.top() << endl;
//	q3.pop();
//
//	cout << *q3.top() << endl;
//	q3.pop();
//
//
//	return 0;
//}


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 模板分离编译 - 一个程序（项目）由若干个源文件共同实现，而每个源文件单独编译生成目标文件，
//                最后将所有目标文件链接起来形成单一的可执行文件的过程称为分离编译模式。

//#include"模板.h"
//
//int main()
//{
//	Add(1, 2);
//	Add(1.0, 2.0);
//	func(1,2);
//	return 0;
//}



